package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-04-29 10:05
 */
public class BX009乘积小于K的子数组 {

    public static void main(String[] args) {

        int[] nums = {10, 5, 2, 6};
        int k = 100;

        System.out.println(numSubarrayProductLessThanK(nums, k));

    }


    /**
     * 使用双指针记录左右坐标
     * <p>
     * 如果左右坐标内的乘积小于k 则右指针往右移 直到乘积大于k 则将左指针往右移
     * <p>
     * 将满足条件的数组记录下来 再拆分数组
     *
     * @param nums
     * @param k
     * @return
     */
    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        List<int[]> list = new ArrayList<>();

        int result = nums[0];
        while (right < nums.length) {
            if (result < k) {
                while (result < k) {
                    right++;
                    //右指针超出范围 则结束 右指针肯定是比左指针先超出范围
                    if (right == nums.length) {
                        list.add(new int[]{left, right - 1});
                        break;
                    }
                    result *= nums[right];
                }
            } else {
                //如果左右指针重合 则说明单个值都不满足条件 则直接两个指针同时往后移动
                if (left == right) {
                    left++;
                    right++;
                    if (right == nums.length) {
                        break;
                    }
                    result = nums[right];
                    continue;
                }else {
                    //将上一符合条件的区间存储起来
                    list.add(new int[]{left, right - 1});
                    while (result >= k) {
                        //右移左指针
                        result /= nums[left];
                        left++;
                    }
                }
            }
        }
        if (list.size() == 0) {
            return 0;
        }

        int[] array = list.get(0);
        int total = nums(array[1] - array[0] + 1);
        for (int i = 1; i < list.size(); i++) {
            int[] array2 = list.get(i);
            //计算重叠区域
            total += nums(array2[1] - array2[0] + 1) - nums(array[1] - array2[0] + 1);
            array = array2;
        }
        return total;
    }

    //计算区间内 可形成的数组数  阶加
    private static int nums(int length) {
        if (length <= 0) {
            return 0;
        }
        if (length == 1) {
            return 1;
        }
        return (1+length)*length/2;
    }
}
